package 动态规划.递归参数思考型;

import org.junit.Test;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/9 14:48
 */
public class lc6912构造最长非递减子数组 {




    /*
      很明显的两种决策问题!
      选择 nums1, 或者选择nums2
     */


    /*
    下面这个 函数的定义:
    f(index, last) :表示的是 从 index  在 状态为 last的时候, 最长连续递增的 长度
    这里的last 表示的是  index 左侧 所做的决策 last = 0 表示 index 是边界 , last = 1 表示选择的是nums1, last = 2 表示选择的是 nums2
    一般这种的 定义的f() 函数 使局部最优, 并不是全局最优!
     */
    public int recursion(int index, int state, int nums1[], int nums2[], Integer dp[][]) {
        if (index == nums1.length) {
            return 0;
        }
        if (dp[index][state] != null) {
            return dp[index][state];
        }
        int ans = 0, pre;
        if (state == 0) {
            pre = 0;
        } else if (state == 1) { // 表示 上一次的决策选中的 是nums1[index]
            pre = nums1[index - 1];

        } else { // state = 1 表示  pre = nums2[index]
            pre = nums2[index - 1];

        }
        if (nums1[index] >= pre) { // 决策①
            ans = recursion(index + 1, 1, nums1, nums2, dp) + 1;
        }
        if (nums2[index] >= pre) { // 决策②
            ans = Math.max(ans, recursion(index + 1, 2, nums1, nums2, dp) + 1);
        }
        return dp[index][state] = ans;
    }

    /*
     记忆化搜索能AC
     */
    public int solve(int nums1[], int nums2[]) {
        int ans = 0;
        Integer[][] dp = new Integer[nums1.length + 1][3];
        for (int i = 0; i < nums1.length; i++) {
            int recursion = recursion(i, 0, nums1, nums2, dp);
            ans = Math.max(ans, recursion);
        }
        return ans;
    }


    /*
     [10,6,13]
     [19,17,11]
     这个过不了!


     现在 这个 又过不了了
     [8,7,4]
     [13,4,4]

     下面这个A不了, 等之后有时间了,可以搞一手 这个!
     */
    public int dp(int nums1[], int nums2[]) {
        int dp[][] = new int[nums1.length + 1][2];
        int max = 0;
        for (int i = nums1.length - 1; i > 0; i--) {
            for (int state = 0; state < 2; state++) {
                int ans = 1, pre;    // 一定要严格审视, 递归函数中 这些中间变量的含义

                 if (state == 0) {
                    pre = nums1[i - 1];
                } else {
                    pre = nums2[i - 1];
                }
                if (nums1[i] >= pre) {
                    ans = Math.max(ans,dp[i + 1][0] + 1);
                }
                if (nums2[i] >= pre) {
                    ans = Math.max(ans, dp[i + 1][1] + 1);
                }
                dp[i][state] = ans;
                max = Math.max(max, ans);
            }
        }
        dp[0][0] = dp[0][1] = Math.max(dp[1][0],dp[1][1]) + 1;
        max = Math.max(dp[0][0],max);


        return max;
    }




    /*
    -
    这种实现跟 上面的实现主要是 f()函数 含义 就不一样

        - 上面的 f(index,last) : 表示的 在 上一个元素 选择 状态 为 state 的时候,再从index 位置 开始做决策的一个最长递增子数组
    -
     换一种 f(index, state) 的定义方式!
     f(index,state) : 表示的含义: 在index 位置上,选择 state 的时候 的最长递增子数组
     f()函数的实现: 一定要严格按照 f() 函数的定义去实现
     */

    public int function(int index,int state,int nums1[],int nums2[]){
        // 因为这不涉及到 上一个元素,也就是 index - 1 的位置, 所以没有边界情况需要考虑
        // 但是 涉及到 index + 1, 这个比较容易判断的多了, 直接 边界控制就可以
        if(index == nums1.length - 1){
            return 1;  // 时刻 想着 f(index, state )的定义
        }
        int ans = 0;

        // 如果state = 0 表示 当前index 位置 选择  nums1
        // 已经确定 index 位置所选的元素的话, 那么 就有一个比较的值了
        if(state == 0){
            if(nums1[index] <= nums1[index + 1]){
                ans = function(index + 1,0,nums1,nums2) + 1;
            }
            if(nums2[index] <= nums2[index + 1]){
                ans = Math.max(function(index + 1,1,nums1,nums2) + 1,ans);
            }
        }else if(state == 1){
            if(nums1[index] <= nums1[index + 1]){
                ans = function(index + 1,0,nums1,nums2) + 1;
            }
            if(nums2[index] <= nums2[index + 1]){
                ans = Math.max(function(index + 1,1,nums1,nums2) + 1,ans);
            }
        }

        return ans == 0 ? 1 : ans;
    }
    /*
     把上面的改成 dp
     */

    public int dpTwo(int nums1[],int nums2[]){
        int len = nums1.length ,dp[][] = new int[len][2],ans = 0;
        dp[len - 1][0] = dp[len -1][1] = 1;

        for(int i = len - 2;i >= 0;i-- ){
            for(int state = 0;state < 2;state++){
                dp[i][state] = 1;
                int cur = state == 0 ? nums1[i] : nums2[i];
                if(cur <= nums1[i + 1]){
                    dp[i][state] = Math.max(dp[i][state],dp[i + 1][0] + 1);
                }
                if(cur <= nums2[i + 1]){
                    dp[i][state] = Math.max(dp[i][state],dp[i + 1][1] + 1);
                }
                ans = Math.max(dp[i][state],ans);
            }
        }
        return ans;
    }


    @Test
    public void test(){
        int nums1[] = {2,3,1};
        int nums2[] = {1,2,1};

        int i = dp(nums1, nums2);
        System.out.println(i);
    }

    /*
     f(index, state) 表示 当前 层在index ,状态 为state 的时候
     state = 0 表示选择 nums1[index] state = 1 表示选择 nums2[index]
     不要去定义上一层状态, 那样会很麻烦
     */
    public int f(int index,int state,int nums1[],int nums2[]){
        if(index == nums1.length){
            return  1;
        }

        int ans = 0;
        if(state == 0){ // nums1[index]
            if(nums1[index] <= nums1[index + 1]){
                ans = f(index + 1,0,nums1,nums2) + 1;
            }
            if(nums1[index] <= nums2[index + 1]){
                ans = Math.max(ans,f(index + 1,1,nums1,nums2) + 1);
            }
        }else{
            if(nums2[index] <= nums1[index + 1]){
                ans = f(index + 1,0,nums1,nums2) + 1;
            }
            if(nums2[index] <= nums2[index + 1]){
                ans = Math.max(ans,f(index + 1,1,nums1,nums2) + 1);
            }
        }
        return ans;
    }


    public int dpFin(int nums1[],int nums2[]){
        int dp[][] = new int[nums1.length][2];
        dp[nums1.length - 1][0] = dp[nums1.length - 1][1] = 1;
        int res = 1;
        for(int index = nums1.length - 2;index >= 0;index--){
            for(int state = 0 ;state <= 1;state++){
                int ans = 1;
                int cur = state == 0 ? nums1[index] : nums2[index];
                if(cur <= nums1[index + 1]){
                    ans = Math.max(ans,dp[index + 1][0] + 1);
                }
                if(cur <= nums2[index + 1]){
                    ans = Math.max(ans,dp[index + 1][1] + 1);
                }
                dp[index][state] = ans;
                res = Math.max(res,dp[index][state]);
            }
        }
        return res;
    }



}
